#define DEBUG 1

/*
 * 十进制整数大数加法和乘法，参数和返回值个位均放到字符串的低位
 * 比如数字 123，则对应的字符串格式应该是 "321"
 */
#include <string>

std::string add(std::string s1, std::string s2) {
    auto        it1   = s1.begin();
    auto        it2   = s2.begin();
    short       carry = 0;
    std::string ans;

    while (it1 != s1.end() || it2 != s2.end() || carry) {
        short x = 0, y = 0;

        if (it1 != s1.end()) x = *it1++ - '0';
        if (it2 != s2.end()) y = *it2++ - '0';

        short res = x + y + carry;
        carry     = res / 10;
        res %= 10;

        ans += res + '0';
    }

    return ans;
}

std::string multiply(std::string s1, std::string s2) {
    std::string   ans;
    unsigned long j = 0;

    for (auto it2 = s2.begin(); it2 != s2.end(); it2++) {
        short       y     = *it2 - '0';
        short       carry = 0;
        std::string tmp;

        for (unsigned long i = 0; i < j; i++) {
            tmp += '0';
        }

        for (auto it1 = s1.begin(); it1 != s1.end(); it1++) {
            short x   = *it1 - '0';
            short res = x * y + carry;
            carry     = res / 10;
            res %= 10;

            tmp += res + '0';
        }

        if (carry) tmp += carry + '0';

        ans = add(ans, tmp);
        j++;
    }

    return ans;
}

std::string qpow(std::string x, unsigned long n) {
    std::string ans = "1";

    while (n) {
        if (n % 2) ans = multiply(ans, x);
        x = multiply(x, x);
        n /= 2;
    }

    return ans;
}

#if DEBUG
#include <algorithm>
#include <iostream>
using namespace std;

int main() {
    string        s1, s2;
    unsigned long n;

    cout << "input s1 s2 n:" << endl;
    cin >> s1 >> s2 >> n;
    reverse(s1.begin(), s1.end());
    reverse(s2.begin(), s2.end());

    string ans = add(s1, s2);
    reverse(ans.begin(), ans.end());
    cout << ans << endl;

    ans = multiply(s1, s2);
    reverse(ans.begin(), ans.end());
    cout << ans << endl;

    ans = qpow(s1, n);
    reverse(ans.begin(), ans.end());
    cout << ans << endl;

    return 0;
}
#endif
